\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}

\title{Advanced Algorithms - Homework Set 2}
\author{Valentina Sintsova \{valentina.sintsova@epfl.ch\} \\ 
        Javier Picorel \{javier.picorel@epfl.ch\} \\
        Vasileios Trigonakis \{vasileios.trigonakis@epfl.ch\} \\}

\begin{document}

\maketitle

\thispagestyle{empty}
\pagestyle{empty}

\paragraph*{Question 1.} (Completing the class analysis of MTF): verify that the competitive ratio of the MTF heuristic remains unchanged even of the optimal algorithm moves some items other than the item accessed.
\\
Use the following simplifying assumptions. There is limited storage available, so that no algorithm, not even OPT, can ``remember'' the location of another element y while accessing
element x. Thus, if y is moved after x (during the access request for x), then y has to be accessed by traversing the list from its head. Recall that the extra storage is needed for free
exchanges. It is used to bring an accessed element x to any location closer to the head of the
list ``for free'', since the algorithm can remember this location while searching the list for x.
Moving any element towards the tail of the list (beyond the original position of the query element
x) uses paid exchanges and is not free. Its cost is proportional to the number of locations
traversed to move it.
\\\\
The simplifying assumption entails that if the OPT algorithm is accessing element x and wants to move-to-front element y during this access, it will have to ``pay'' for a normal search of y. The outcome of this, is that moving the y in front while accessing x cannot bring performance benefits to OPT. Why is that?

The only reason why OPT may decide to bring an element y in front is because y will be accessed at least once in the future. Since y will be accessed anyway, bringing it in front earlier than the first access can only degrade the performance, therefore OPT would never take such a decision.

On the contrary, moving an element backwards could increase the performance of the upcoming searches, by reducing the length of the structure that has to be parsed. If the arrays look like the following before the operation:

\begin{center}
\begin{figure}[hbtp]
\includegraphics[width=1\linewidth]{mtf1.png}
\end{figure}
\end{center}
we have $\Phi_{i} = j + l$. Assuming that OPT decides not to move x, but another element y backwards, we get the following figure:

\begin{center}
\begin{figure}[hbtp]
\includegraphics[width=1\linewidth]{mtf2.png}
\end{figure}
\end{center}
The actual costs are the following:\\\\
$C_{MTF} = k + l + 1\\
C_{OPT} = k + j + b1 + b2
$\\\\
and the new potential is $\Phi_{i+1} = k + j + b2 (-1)$. The -1 is optional and depends to if y is an element before x (for OPT) and is brought after x. So, we get:\\\\
$C_{MTF} + \Delta\Phi =
k + l + 1 + k + j + b2 - j - l = 
2k + 1 + b2 \leq
2(k + l + b1 + b2 +1) - 1 =
2C_{OPT} - 1
$\\\\
Even if OPT decides to move more than one elements backwards and/or if OPT is not static regarding x, the results would be very similar.



\paragraph*{Question 5.} Consider this alternative way of inserting a new key x into a splay tree: we search for the key x, arriving at a nil pointer; we attach a node containing key x to this nil pointer, and promote this node to the root using the splay patterns. In effect, this is a regular splay operation, except that we ``sneak in'' a quick insertion of a node. Verify that this method of insertion also takes logarithmic amortized time (pay attention to what happens to the potential).
\\\\
In order to perform the insertion, we need to do a search for the place that the element will be inserted first. Since, an splay operation performs the same steps and is actually a more expensive operation, we know that the search has also amortized cost of $logn$.

Then, we will bound the $\Delta\Phi$ that the insertion causes. The insertion increases the weight of each of the nodes in the path to the insertion point by 1. So,\\\\
$\forall x \epsilon Path : w'(x) = w(x) + 1 \Rightarrow \\
\forall x \epsilon Path : r'(x) = log(w'(x)) = log(w(x) + 1)$\\\\
The newly inserted node has $w(x) = 1 \Rightarrow r(x) = 0$. Every node not belonging to the path does not get affected. Therefore,\\
\[
\left.\Phi_{i} = \Phi_{path_{i}} + \Phi_{other_{i}}, \\
\Phi_{i+1} = \Phi_{path_{i+1}} + \Phi_{other_{i}} \right| \Rightarrow 
\Delta\Phi = \Phi_{path_{i+1}} - \Phi_{path_{i}} \Rightarrow\]
\[
\Rightarrow \Delta\Phi = \sum_{x \epsilon Path}log(w(x) + 1) - \sum_{x \epsilon Path}log(w(x)) =
\]
\[
= \sum_{x \epsilon Path}log(\dfrac{w(x) + 1}{w(x)})
\]
\\But, $max(log(\dfrac{n + 1}{n}) = 1)$, for $n = 1$ and it is a decreasing function, thus in order to take the maximum value of the sum, we should input as many small values as possible. Obviously, the most unbalanced  binary tree (linked-list) holds this property, thus maximizing the sum:\\\\
$
\Delta\Phi = \sum_{x \epsilon Path}log(\dfrac{w(x) + 1}{w(x)}) \leq \sum_{x = 1}^{x = n}log(\dfrac{x + 1}{x}) =\\\\
= \sum_{x = 1}^{x = n}(log(x + 1) - log(x)) = log(n + 1) - log(1) = log(n+1)
$
\\\\
So, since the amortized cost for searching the element is $logn$, the maximum change in the potential is also $logn$ \footnote{$log(n+1)$ to be precise}, and the splay operation has $logn$ amortized cost, we can infer that this way of performing an insertion has also $logn$ amortized cost.














\end{document}
